#include "main/utils.h"
using namespace std;

int minCoins1(const vector<int>& coins, const int& target) {
  int len = coins.size();
  vector<int> dp(target + 1, target + 1);
  dp[0] = 0;
  for (int i = 1; i <= len; ++i) {
    for (int j = target; j >= 1; --j) {
      for (int k = 1; k * coins[i - 1] <= j; k++) {
        dp[j] = min(dp[j], dp[j - k * coins[i - 1]] + k);
      }
    }
  }
  return dp[target] > target ? -1 : dp[target];
}

int minCoins2(const vector<int>& coins, const int& target) {
  int len = coins.size();
  vector<int> dp(target + 1, target + 1);
  dp[0] = 0;
  for (int i = 1; i <= target; ++i) {
    for (int j = 0; j < len; ++j) {
      if (i >= coins[j])
        dp[i] = min(dp[i], dp[i - coins[j]] + 1);
    }
  }
  return dp[target] > target ? -1 : dp[target];
}

int main() {
  vector<int> coins = {1, 3, 9, 10};
  cout << minCoins1(coins, 15) << endl;
  cout << minCoins2(coins, 15) << endl;

  return 0;
}
